package com.lft.linked.list02.double_ended_linked_list;

/**
 * 双端链表
 */
public class DoubleEndedLinkedListDemo {
	public static void main(String[] args) {
		DoubleEndedLinkedList list = new DoubleEndedLinkedList();
		int[] a = {1, 5, 6, 7, 2, 3, 9, 4, 8};
		for (int i = 0; i < a.length; i++) {
			if ((i & 2) == 0) {
				list.insertFirst(new Node(a[i]));
			} else {
				list.insertLast(new Node(a[i]));
			}
		}
		list.displayList();
		list.deleteFirst();
		list.displayList();
	}
}

class DoubleEndedLinkedList {
	private Node first;
	private Node last;
	
	public DoubleEndedLinkedList() {
		this.first = null;
		this.last = null;
	}
	
	/**
	 * 判断链表是否为空
	 * @return true:链表为空，false:链表不为空
	 */
	public boolean isEmpty() {
		return first == null;
	}
	
	/**
	 * 从头部插入
	 * @param node 要插入的节点
	 */
	public void insertFirst(Node node) {
		if (isEmpty()) {
			this.last = node;
		}
		node.setNext(this.first);
		this.first = node;
	}
	
	/**
	 * 从尾部插入
	 * @param node 要插入的节点
	 */
	public void insertLast(Node node) {
		if (isEmpty()) {
			first = node;
		} else {
			last.setNext(node);
		}
		last = node;
	}
	
	/**
	 * 删除第一个节点
	 * @return 删除的节点
	 */
	public Node deleteFirst() {
		Node temp = this.first;
		if (this.first.getNext() == null) {
			last = null;
		}
		first = first.getNext();
		return temp;
	}
	
	/**
	 * 遍历双端链表
	 */
	public void displayList() {
		Node curNode = first;
		while (curNode != null) {
			curNode.displayNode();
			curNode = curNode.getNext();
		}
		System.out.println();
	}
	
}

class Node {
	private int data;
	private Node next;
	
	public Node(int data) {
		this.data = data;
	}
	
	public int getData() {
		return data;
	}
	
	public void setData(int data) {
		this.data = data;
	}
	
	public Node getNext() {
		return next;
	}
	
	public void setNext(Node next) {
		this.next = next;
	}
	
	public void displayNode() {
		System.out.print(this.getData() + " -> ");
	}
	
	@Override
	public String toString() {
		return "Node{" +
				"data=" + data +
				'}';
	}
}